//给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。 
//
// 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？ 
//
// 
//
// 示例 1： 
//
// 输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
// 
//
// 示例 2： 
//
// 输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
// 
//
// 示例 3： 
//
// 输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
// 
//
// 示例 4： 
//
// 输入：nums1 = [], nums2 = [1]
//输出：1.00000
// 
//
// 示例 5： 
//
// 输入：nums1 = [2], nums2 = []
//输出：2.00000
// 
//
// 
//
// 提示： 
//
// 
// nums1.length == m 
// nums2.length == n 
// 0 <= m <= 1000 
// 0 <= n <= 1000 
// 1 <= m + n <= 2000 
// -106 <= nums1[i], nums2[i] <= 106 
// 
// Related Topics 数组 二分查找 分治算法 
// 👍 3449 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int size = nums1.length+nums2.length;
        if (size%2==0)
        {
            int left=found(nums1,0,nums2,0,size/2);
            int right = found(nums1, 0, nums2, 0, size / 2+1);//偶数分为左右两个数
            return (left+right)/2.0;
        }
        else {
            return found(nums1, 0, nums2, 0, size / 2+1);
        }
    }
    public static int found (int[] nums1,int i,int []nums2,int j,int k){//寻找特殊情况更好判界值
        if(nums1.length-i>nums2.length-j) return found(nums2,j,nums1,i,k);//默认第一个数组长度小于第二个 如果不是，则交换位置
        if (nums1.length-i==0){ return nums2[k+j-1];        }//该数据只能在nums2 中找到
        if(k==1) return Math.min(nums1[i],nums2[j]);//找到最小的那个数
        int si=Math.min((int)nums1.length,i+k/2);//防止数组越界
        int sj=j+k / 2;
        if(nums1[si-1]>nums2[sj-1]){//找到中间那个数进行比较
            return found(nums1,i,nums2,sj,k-(sj-j));
        }
        else {
            return found(nums1, si, nums2, j, k-(si-i));//第一个数组长度较小 特殊处理
        }
    }

}
//leetcode submit region end(Prohibit modification and deletion)
